package dfs;

import sun.font.TrueTypeFont;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * https://leetcode-cn.com/problems/permutations-ii/submissions/
 * @author: luo
 * @email: luo@nyist.edu.cn
 * @date: 2021/1/14 12:03
 */
public class PermuteUnique {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permuteUnique(nums));
    }

    public static List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        backtracking(1, nums, new ArrayList<Integer>(), new int[nums.length], lists);
        return lists;
    }
    /**
     * 使用子集树作为搜索树
     * 限界条件：结果中不得出现重复排列
     * @param t
     * @param nums
     * @param list 存放当前解
     * @param strack 标记数字是否已在列表中
     * @param lists 存放解
     */
    private static void backtracking(int t, int nums[], List<Integer> list, int[] strack, List<List<Integer>> lists) {
        int len = nums.length;
        if (t > len) {
            lists.add(new ArrayList<>(list));
        } else {
            int[] inNums = new int[len];
            boolean flag = false;
            for (int i = 0; i < len; i++) {
                if (strack[i] == 0) {
                    //判断nums[i]是否是重复出现的数字
                    flag = false;
                    for (int j = 0; j < len; j++) {
                        if (inNums[j] == 1 && nums[j] == nums[i]) {
                            flag = true;
                            break;
                        }
                    }
                    if (flag) continue;
                    //当前数字可加入解空间树
                    inNums[i] = 1;
                    list.add(nums[i]);
                    strack[i] = 1;
                    backtracking(++t, nums, list, strack, lists);//进入下一层
                    //回溯
                    --t;
                    list.remove(list.size() - 1);
                    strack[i] = 0;
                }
            }

        }
    }

}
